package com.kevinkk.stackandqueue;

import java.util.Deque;
import java.util.ArrayDeque;

/**
 * 给出由小写字母组成的字符串 s，重复项删除操作会选择两个相邻且相同的字母，并删除它们。
 * 在 s 上反复执行重复项删除操作，直到无法继续删除。
 * 在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
 */

public class RemoveAllAdjacentDuplicatesInString {
    class Solution {
        public String removeDuplicates(String s) {
            Deque<Character> st = new ArrayDeque<>();
            char[] cs = s.toCharArray();
            for (char c : cs) {
                if (!st.isEmpty() && c == st.peekFirst()) { // 有重复的，则不仅删除栈顶元素，而且新的元素也不入栈
                    st.removeFirst();
                } else {
                    st.addFirst(c);
                }
            }
            StringBuilder sb = new StringBuilder();
            while (!st.isEmpty())
                // 逆向输出
                sb.append(st.removeLast());
            return sb.toString();
        }
    }
}
